/*
 * Solution.cpp
 *
 *  Created on: May 26, 2012
 *      Author: hugo
 */

#include "Solution.h"
#include <stack>
using namespace std;

Solution::Solution(Instance *_instance) {
	instance = _instance;
	nodes = (int*)malloc(sizeof(int)*_instance->num_vertex());
	for(long i=0;i<_instance->num_vertex();i++){
		nodes[i]=0;
	}

	edges = (int*)malloc(sizeof(int)*_instance->num_edge());
	for(long i=0;i<_instance->num_edge();i++){
		edges[i]=0;
	}
	prize=0;
	cost=0;
}

pair<float,vector<Edge*> > Solution::diff(Solution *sol){
	vector<Edge*> edges;
	pair<float,vector<Edge*> > ds = make_pair(0,edges);
	typedef pair<float,vector<Vertex*> > path;
	queue<path> fila;
	Vertex *st = instance->get_vertex(get_edge(0)->get_i());
	//cout << "Start by" << get_edge(0)->get_i() <<endl;
	vector<Vertex*> sub;
	sub.push_back(st);
	fila.push(make_pair(0,sub));

	path best = fila.front();
	int *nodes_enque = (int*)malloc(sizeof(int)* instance->num_vertex());
	for(long i=0;i<instance->num_vertex();i++){
		nodes_enque[i]=0;
	}
	nodes_enque[st->get_id()] = 1;
	bool found=false;
	while(!fila.empty()){
		path elem = fila.front();
		fila.pop();
		sub = elem.second;
		Vertex *v = sub.at(sub.size()-1);
		if(sol->has_vertex(v)){
			float test_val = elem.first+sol->cost-sol->prize;
			/*cout << "Achou "<< v->get_id() << " "<< test_val <<endl;
			for(unsigned int i=0;i<sub.size()-1;i++){
				Vertex *n1 = elem.second.at(i);
				Vertex *n2 = elem.second.at(i+1);
				cout << "("<<(n1->get_id()+1)<<","<<(n2->get_id()+1)<<")"<<endl;
			}
			cout << "------"<<endl;*/
			if(!found || test_val<best.first){
				found=true;
				best = elem;
			}
		}
		for(int i=0;i<instance->num_vertex();i++){
			Edge *e = instance->get_edge(v->get_id(),i);
			Vertex *v2 = instance->get_vertex(i);
			if(e!=NULL && !nodes_enque[v2->get_id()]){
				vector<Vertex*> sub2(sub.begin(),sub.end());
				sub2.push_back(v2);
				float val = elem.first;
				if(!has_vertex(v2)){
					val+= e->get_cost();
				}
				if(!has_vertex(v2) && !sol->has_vertex(v2)){
					val-= v2->get_prize();
				}
				fila.push(make_pair(val,sub2));
				nodes_enque[v2->get_id()]=1;
			}
		}
	}
	sub = best.second;
	ds.first = best.first+sol->cost-sol->prize;
	//cout << "Diff val: " << ds.first << endl;
	for(unsigned int i=0;i<sub.size()-1;i++){
		Vertex *n1 = sub.at(i);
		Vertex *n2 = sub.at(i+1);
		//cout << "("<<(n1->get_id()+1)<<","<<(n2->get_id()+1)<<")"<<endl;
		Edge *e = instance->get_edge(n1->get_id(),n2->get_id());
		ds.second.push_back(e);
	}
	//cout << "-------"<<endl;
	//cout << (found?"Achou":"Nao achou") <<endl;
	free(nodes_enque);
	return ds;
}
bool Solution::has_edge(Edge* e){
	return has_edge(e->get_id());
}
bool Solution::has_edge(int i){
	return edges[i];
}

void Solution::apply(pair<float,vector<Edge*> > ds, Solution *sol){
	for(unsigned int i=0;i<ds.second.size();i++){
		add_edge(ds.second.at(i));
	}
	for(unsigned int i=0;i<sol->tree.size();i++){
		add_edge(sol->tree.at(i));
	}
}

void Solution::add_vertex(int i){
	if(!nodes[i]){
		prize+=instance->get_vertex(i)->get_prize();
		nodes[i]=1;
	}
}

void Solution::add_edge(Edge *edge){
	if(has_edge(edge))
		return;
	tree.push_back(edge);
	edges[edge->get_id()]=1;
	int i = edge->get_i();
	int j = edge->get_j();
	if(!nodes[i]){
		prize+=instance->get_vertex(i)->get_prize();
		nodes[i]=1;
	}else
		i=-1;
	if(!nodes[j]){
		prize+=instance->get_vertex(j)->get_prize();
		nodes[j]=1;
	}else
		j=-1;
	cost+=edge->get_cost();
}
float Solution::get_value(){
	prize=0;
	for(int i=0;i<instance->num_vertex();i++)
		if(has_vertex(i))
			prize+=instance->get_vertex(i)->get_prize();
	//cout << "Total2: "<< instance->get_total_prize() <<endl;
	//cout << "Cost2: "<<cost<<endl;
	//cout << "Prize2: "<<prize<<endl;
	return cost+(instance->get_total_prize()-prize);
}

bool Solution::has_vertex(int i){
	return nodes[i];
}

bool Solution::has_vertex(Vertex* v){
	return has_vertex(v->get_id());
}

bool Solution::is_better(Edge *edge){
	int i = edge->get_i();
	int j = edge->get_j();
	int tmp_prize = prize;
	int tmp_cost = cost;
	if(!nodes[i]){
		tmp_prize+=instance->get_vertex(i)->get_prize();
	}
	if(!nodes[j]){
		tmp_prize+=instance->get_vertex(j)->get_prize();
	}
	tmp_cost+=edge->get_cost();

	//return prize/cost > tmp_prize/tmp_cost;
	return get_value() > tmp_cost+(instance->get_total_prize()-tmp_prize);
}

bool Solution::is_valid(){
	stack<Vertex*> pilha;
	int init=-1;
	int *found = (int*)malloc(sizeof(int)*instance->num_vertex());
	int *at_stack = (int*)malloc(sizeof(int)*instance->num_vertex());

	for(long i=0;i<instance->num_vertex();i++){
		found[i]=0;
		at_stack[i]=0;
		if(nodes[i])
			init=i;
	}
	if(init>=0){
		pilha.push(instance->get_vertex(init));
		at_stack[init]=1;
		found[init]=1;
		bool ciclo=false;
		while(!pilha.empty()){
			Vertex *v = pilha.top();
			pilha.pop();
			at_stack[v->get_id()]=0;
			//cout << "Analise "<<(v->get_id()+1)<<endl;
			for(int i=0;i<instance->num_vertex();i++){
				Edge *e=instance->get_edge(i,v->get_id());
				if(e!=NULL && has_vertex(i)){
					bool has=false;
					for(unsigned int j=0;j<tree.size() && !has;j++){
						if(get_edge(j)==e)has=true;
					}
					if(has){
						if(at_stack[i]){
							cout << "Ciclo"<<endl;
							ciclo=true;
						}
						//cout << "Vizinho "<< (i+1)<<endl;
						//cout << "TEM "<< "("<< (e->get_i()+1) <<","<< (e->get_j()+1) <<")"<<endl;
						if(!found[i]){
							found[i]=1;
							at_stack[i]=1;
							pilha.push(instance->get_vertex(i));
						}
					}
				}
			}
		}
		for(long i=0;i<instance->num_vertex();i++){
			if(found[i]!=nodes[i]){
				return false;
			}
		}
		return true && !ciclo;
	}else
		return true;
	return false;
}

Solution::~Solution() {
	// TODO Auto-generated destructor stub
}

Edge* Solution::get_edge(int i){
	return tree.at(i);
}
int Solution::size(){
	return tree.size();
}

float Solution::get_cost(){
	return cost;
}
float Solution::get_prize(){
	return prize;
}
void Solution::print(){
	cout << "Solution valid? " << (is_valid()?"YES":"NO") <<endl;
	cout << "Solution cost: " << get_value()<<endl;
	for(int i=0;i<size();i++){
		cout <<"(" <<get_edge(i)->get_i()+1<<","<<get_edge(i)->get_j()+1 <<") , ";
	}
	cout << endl;
}
void Solution::quick_print(){
	if(is_valid())
		cout << "Solution cost: " << get_value()<<endl;
	else
		cout << "Solution cost: INVALID"<<endl;
}
